package leetcode.graph.hamilton.p980;
/**
 * 
 * @Title: Solution.java 
 * @Package leetcode.graph.hamilton 
 * @Description: 980. 不同路径 III
 *                  参考题解：记录起始和终止位置的索引，并将二维数组的索引压缩成一维数组的索引
 * @author CandyWall   
 * @date 2021年1月19日 下午1:05:22 
 * @version V1.0
 */
class Solution_v1 {
    private int R;
    private int C;
    private int[][] grid;
    private boolean[][] visited;
    private int start, end;
    private int[][] dirs = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};
    public int uniquePathsIII(int[][] grid) {
        this.grid = grid;
        R = grid.length;
        C = grid[0].length;
        visited = new boolean[R][C];
        // 找出起始位置，并且统计空方格的个数
        int left = R * C;
        
        for(int i = 0; i < R; i++) {
            for(int j = 0; j < C; j++) {
                if(grid[i][j] == 1) {
                    start = i * C + j;
                    grid[i][j] = 0;
                } else if(grid[i][j] == 2) {
                    end = i * C + j;
                    grid[i][j] = 0;
                } else if(grid[i][j] == -1) {
                    left--;
                }
            }
        }
        
        System.out.println(left);
        
        return dfs(start, left);
    }
    
    private int dfs(int v, int left) {
        int x = v / C, y = v % C;
        left--;
        visited[x][y] = true;
        if(left == 0 && v == end) {
            visited[x][y] = false;
            return 1;
        }
        int res = 0;
        for(int d = 0; d < 4; d++) {
            int nextX = dirs[d][0] + x;
            int nextY = dirs[d][1] + y;
            if(inArea(nextX, nextY) && !visited[nextX][nextY] && grid[nextX][nextY] == 0) {
                res += dfs(nextX * C + nextY, left);
            } 
        }
        
        visited[x][y] = false;
        
        return res;
    }
    
    // 判断二维数组的索引是否合法
    private boolean inArea(int x, int y) {
        return x >= 0 && x < R && y >= 0 && y < C;
    }
    
    public static void main(String[] args) {
        System.out.println(new Solution_v1().uniquePathsIII(new int[][] {{1,0,0,0}, {0,0,0,0}, {0,0,2,-1}}));
    }
}